《离散数学》期末试卷 (精选09)
一、判断题（共 10 小题，每题 1 分，共 10 分）
- 设 $p$、$q$ 为任意命题公式，则 $(p \wedge q) \vee p \Leftrightarrow p$ （ ）
查看答案与解析
答案：$\sqrt{}$（正确）
【解析】
- 定律识别：本题考查命题逻辑中的 吸收律 (Absorption Law)。
- 等价演算：
- $(p \wedge q) \vee p$
- $\equiv p \vee (p \wedge q)$ （交换律）
- $\equiv p$ （直接应用吸收律）
- 真值表验证：
- 当 $p$ 为 $F$ 时：$(F \wedge q) \vee F \equiv F \vee F \equiv F$。
- 当 $p$ 为 $T$ 时：$(T \wedge q) \vee T \equiv q \vee T \equiv T$。
- 结果始终与 $p$ 相同，故等价成立。
解题套路总结：在化简包含嵌套结构的命题公式时，优先寻找是否有公共项。若形式符合 $A \vee (A \wedge B)$ 或 $A \wedge (A \vee B)$，则可立即吸收冗余项。
难度： ⭐ 考点： #等价演算 #吸收律
💡 学习锦囊
📖 相关公式：
- 吸收律：$p \vee (p \wedge q) \Leftrightarrow p$；$p \wedge (p \vee q) \Leftrightarrow p$。
思路分析
观察题目结构：内层是合取（$\wedge$），外层是析取（$\vee$），且内外层共享一个公共变元 $p$。这是吸收律的标准应用场景。
🔄 举一反三
判断：$p \vee (\neg p \wedge q) \Leftrightarrow p \vee q$ （ ）
查看练习答案与解析
答案：$\sqrt{}$解析：
- 使用分配律：$(p \vee \neg p) \wedge (p \vee q)$。
- 根据排中律：$p \vee \neg p \equiv T$。
- 根据恒等律：$T \wedge (p \vee q) \equiv p \vee q$。
- $\forall x(F(y) \rightarrow G(x)) \Leftrightarrow F(y) \rightarrow \exists x G(x)$ （ ）
查看答案与解析
答案：$\times$（错误）
【解析】
- 量词性质：左侧全称量词 $\forall x$ 作用于整个括号内容。
- 等价转换：由于前提 $F(y)$ 中不含变元 $x$，根据量词辖域收缩规则： $\forall x(F(y) \rightarrow G(x)) \equiv F(y) \rightarrow \forall x G(x)$。
- 对比分析：
- 左边推导结论是 $\forall x G(x)$。
- 右边给出结论是 $\exists x G(x)$。
- 在非空论域下，$\forall x G(x) \implies \exists x G(x)$，但反之不成立。因此两者不等价。
解题套路总结：量词从蕴含式的结论部分移动时，其性质（$\forall$ 或 $\exists$）保持不变；但若从前提部分移动，则需发生翻转。
难度： ⭐⭐ 考点： #谓词逻辑 #量词辖域收缩
💡 学习锦囊
📖 相关公式（$x$ 不在 $A$ 中自由出现）：
- $\forall x(A \rightarrow B(x)) \Leftrightarrow A \rightarrow \forall x B(x)$
- $\forall x(B(x) \rightarrow A) \Leftrightarrow \exists x B(x) \rightarrow A$
思路分析
判断此类等价式时，首先看量词所在的“位置”。本题中量词在结论处，移动时不应改变性质。
🔄 举一反三
判断：$\exists x(F(y) \vee G(x)) \Leftrightarrow F(y) \vee \exists x G(x)$ （ ）
查看练习答案与解析
答案：$\sqrt{}$解析：当 $x$ 不在 $F(y)$ 中自由出现时，存在量词可直接对析取项进行分配。
- 初级回路一定是简单回路。（ ）
查看答案与解析
答案：$\sqrt{}$（正确）
【解析】
- 定义辨析：
- 初级回路：除起点和终点外，顶点互不相同（即点不重复）。
- 简单回路：边互不相同（即边不重复）。
- 包含关系推导：
- 如果一个回路中的顶点都不重复，那么由于连接这些顶点的边集合也是唯一的（在简单图中）或在访问路径中边无法被重复使用（在多重图中若要重复边则必须回到已访问过的点）。
- 换言之，点不重复必然意味着边不重复。因此初级回路必定是简单回路。
- 注意：反之不成立，简单回路可以经过重复的顶点（如“8”字形路径）。
解题套路总结：图论概念的严谨性：初级通路/回路 $\subset$ 简单通路/回路 $\subset$ 一般通路/回路。
难度： ⭐ 考点： #图论基础 #初级回路 #简单回路
💡 学习锦囊
📖 相关知识点：
- 初级：限制顶点不重复。
- 简单：限制边不重复。
思路分析
“点不重”是比“边不重”更强的限制条件。强的条件一定能满足弱的条件。
- 自然映射是双射。（ ）
查看答案与解析
答案：$\times$（错误）
【解析】
- 定义回顾：自然映射 $g: A \rightarrow A/R$ 定义为 $g(a) = [a]_R$。
- 性质分析：
- 满射性：商集中的每个等价类至少有一个代表元，故自然映射一定是满射。
- 单射性：如果等价关系 $R$ 使得某些不同的元素 $a, b$ 属于同一类（即 $aRb$），则 $g(a)=g(b)$，导致映射不是单射。
- 结论：除非 $R$ 是恒等关系 $I_A$，否则自然映射通常不是单射，因此不是双射。
解题套路总结：等价类和商集的核心逻辑是“分类归纳”，这本质上是一个“多对一”的过程，通常会丢失单射性。
难度： ⭐⭐ 考点： #等价关系 #自然映射 #商集
💡 学习锦囊
📖 相关知识点：
- 恒等映射是双射。
- 自然映射通常仅为满射。
思路分析
将“自然映射”类比为“户口登记”，每个人都映射到自己的家庭。每个家庭都有人（满射），但一个家庭可能有很多人（非单射）。
IMPORTANT
注：原试卷第 5-12 题缺失，以下直接从第 13 题开始。
二、填空题（共 8 小题，每题 2 分，共 16 分）
- $p \leftrightarrow q$ 的主合取范式是 ________。
查看答案与解析
答案：$(\neg p \vee q) \wedge (p \vee \neg q)$
【解析】
- 展开等价式：$p \leftrightarrow q \equiv (p \rightarrow q) \wedge (q \rightarrow p)$。
- 利用消蕴含律：$(\neg p \vee q) \wedge (\neg q \vee p)$。
- 规范化排序：整理为 $(\neg p \vee q) \wedge (p \vee \neg q)$。
- 对应极大项：$M_1 \wedge M_2$（二进制编码 01 和 10）。
解题套路总结：求主合取范式最稳妥的方法是看真值表。$p \leftrightarrow q$ 在 (0,1) 和 (1,0) 时为假，对应的极大项分别是 $M_1$ 和 $M_2$。
难度： ⭐⭐ 考点： #主合取范式 #极大项
💡 学习锦囊
📖 相关公式：
- $p \leftrightarrow q \equiv (p \wedge q) \vee (\neg p \wedge \neg q)$（这是主析取范式）。
思路分析
主合取范式由极大项合取而成。只要找出真值表中结果为 $0$ 的行，根据变量取值（$0$ 对应原变量，$1$ 对应否定项）写出析取项即可。
- 完全二部图 $K_{r,s}$ ($r < s$) 的边连通度等于 ________。
查看答案与解析
答案：$r$
【解析】
- 参数识别：$K_{r,s}$ 有两个顶点组，规模分别为 $r$ 和 $s$。
- 最小度分析：第一组顶点度数均为 $s$，第二组顶点度数均为 $r$。因 $r < s$，故最小度 $\delta = r$。
- 定理结论：对于完全二部图，点连通度 $\kappa = $ 边连通度 $\lambda = $ 最小度 $\delta = r$。
解题套路总结：对于典型的对称图，连通度通常直接取其最小度。
难度： ⭐⭐ 考点： #边连通度 #完全二部图
- 设 $A = \{a, b\}$，则 $A$ 上共有 ________ 个不同的偏序关系。
查看答案与解析
答案：3
【解析】
- 自反性要求：必须包含对角线元素 $\{\langle a,a \rangle, \langle b,b \rangle\}$。
- 反对称性限制：不能同时包含 $\langle a,b \rangle$ 和 $\langle b,a \rangle$。
- 可能的关系集合：
- $R_1 = \{\langle a,a \rangle, \langle b,b \rangle\}$
- $R_2 = \{\langle a,a \rangle, \langle b,b \rangle, \langle a,b \rangle\}$
- $R_3 = \{\langle a,a \rangle, \langle b,b \rangle, \langle b,a \rangle\}$
- 验证：这三个集合均满足自反、反对称和传递性。
解题套路总结：计数类问题建议分层讨论：先固定必选项（自反项），再按边数（0条, 1条...）递增讨论非自反项。
难度： ⭐⭐⭐ 考点： #偏序关系 #关系计数
- 模 6 加群 $\langle \mathbb{Z}_6, \oplus \rangle$ 中，4 是 ________ 阶元。
查看答案与解析
答案：3
【解析】
- 定义计算：寻找最小正整数 $n$ 使 $n \cdot 4 \equiv 0 \pmod 6$。
- $1 \cdot 4 = 4$
- $2 \cdot 4 = 8 \equiv 2$
- $3 \cdot 4 = 12 \equiv 0 \pmod 6$
- 结论：阶为 3。
解题套路总结：利用公式法秒杀：$\text{ord}(a) = \frac{m}{\text{gcd}(a, m)} = \frac{6}{\text{gcd}(4, 6)} = 3$。
难度： ⭐ 考点： #元素的阶 #循环群
- 设 $A = \{1,2,3,4,5\}$ 上的关系 $R = \{\langle 1,3 \rangle, \langle 1,5 \rangle, \langle 2,5 \rangle, \langle 3,3 \rangle, \langle 4,5 \rangle\}$，则 $R$ 的传递闭包 $t(R) = $ ________。
查看答案与解析
答案：$\{\langle 1,3 \rangle, \langle 1,5 \rangle, \langle 2,5 \rangle, \langle 3,3 \rangle, \langle 4,5 \rangle\}$
【解析】
- 定义判断：传递闭包 $t(R)$ 需满足若 $aRb$ 且 $bRc$，则必须有 $aRc$。
- 检查路径：
- 唯一的链式路径是 $\langle 1,3 \rangle$ 且 $\langle 3,3 \rangle$。其推导结果为 $\langle 1,3 \rangle$，已在 $R$ 中。
- 其他元素 $5$ 作为终点，没有出度。
- 结论：$R$ 本身已满足传递性，故其闭包就是自身。
解题套路总结：检查传递性时，重点观察那些“既是终点又是起点”的顶点。如果它们没有带出新的边，则闭包不变。
难度： ⭐⭐ 考点： #传递闭包 #关系矩阵
- 已知有向图 $D$ 的度数列为 $(2,3,2,3)$，出度列为 $(1,2,1,1)$，则有向图 $D$ 的入度列为 ________。
查看答案与解析
答案：$(1,1,1,2)$
【解析】
- 公式应用：有向图中 $d(v) = d_{in}(v) + d_{out}(v)$。
- 计算：
- $v_1: 2 - 1 = 1$
- $v_2: 3 - 2 = 1$
- $v_3: 2 - 1 = 1$
- $v_4: 3 - 1 = 2$
- 结果：$(1,1,1,2)$。
难度： ⭐ 考点： #入度 #出度 #图的度数
- $n$ 阶无向简单连通图 $G$ 的生成树有 ________ 条边。
查看答案与解析
答案：$n-1$
【解析】 根据树的定义：$n$ 个节点的树恰好有 $n-1$ 条边。作为原图的子图且包含所有顶点，生成树必须满足此基本性质。
难度： ⭐ 考点： #生成树 #树的边数
- 7 阶圈的点色数是 ________。
查看答案与解析
答案：3
【解析】 对于圈图 $C_n$：
- 若 $n$ 为偶数，$\chi(G) = 2$。
- 若 $n$ 为奇数，$\chi(G) = 3$。 本题中 $n=7$（奇数），故需 3 种颜色。
难度： ⭐ 考点： #点色数 #圈图着色
三、运算题（共 5 小题，每小题 8 分，共 40 分）
- 求 $\exists x F(x) \rightarrow \exists y G(x, y)$ 的前束范式。
查看答案与解析
答案：$\forall x_1 \exists y (\neg F(x_1) \vee G(x, y))$
详细推导：
- 消去蕴含：$\neg (\exists x F(x)) \vee \exists y G(x, y)$
- 内移否定：$\forall x \neg F(x) \vee \exists y G(x, y)$
- 变量换名：原式右侧包含自由变元 $x$，左侧量词变量也为 $x$，为避免冲突，将左侧 $x$ 换名为 $x_1$。 $\forall x_1 \neg F(x_1) \vee \exists y G(x, y)$
- 提取量词：$\forall x_1 \exists y (\neg F(x_1) \vee G(x, y))$
解题套路总结：转换前束范式务必检查“换名”步骤。量词提取时，量词变量不能在其余部分自由出现。
难度： ⭐⭐ 考点： #前束范式 #量词移动规则
💡 学习锦囊
易错点
若不换名直接提取为 $\forall x \exists y (\dots)$，会导致原本自由的 $x$ 被错误约束，改变了公式的逻辑意义。
- 已知无向图 $G$ 有 11 条边，2 度和 3 度顶点各两个，其余为 4 度顶点，求 $G$ 的顶点数。
查看答案与解析
答案：7
详细推导：
- 握手定理：$\sum d(v) = 2 \times |E| = 22$。
- 列方程：设 4 度顶点有 $k$ 个。 $2 \times 2 + 2 \times 3 + 4k = 22$$4 + 6 + 4k = 22 \implies 4k = 12 \implies k = 3$。
- 总结顶点数：总数 $n = 2 + 2 + 3 = 7$。
难度： ⭐ 考点： #握手定理 #图的度数计算
- 设 $A = \{a,b,c,d,e,f\}$，$R = I_A \cup \{\langle a,b \rangle, \langle b,a \rangle\}$，已知 $R$ 是 $A$ 上的等价关系。求等价类 $[a]_R$、$[c]_R$ 及商集 $A/R$。
查看答案与解析
答案：
- $[a]_R = \{a, b\}$
- $[c]_R = \{c\}$
- $A/R = \{\{a, b\}, \{c\}, \{d\}, \{e\}, \{f\}\}$
详细推导：
- 求等价类：寻找所有与 $a$ 相关的元素。由 $I_A$ 有 $aRa$，由 $\langle a,b \rangle$ 有 $aRb$。故 $[a]_R = \{a, b\}$。
- 求等价类：寻找所有与 $c$ 相关的元素。仅有 $\langle c,c \rangle \in I_A$。故 $[c]_R = \{c\}$。
- 列出商集：商集是所有不相交等价类的集合。
难度： ⭐ 考点： #等价类 #商集
- 求图示带权图中的最小生成树，并计算最小生成树的权。
查看答案与解析
答案：最小生成树的总权值为 12
详细推导（Kruskal 算法）：
- 列出所有边权重（按升序）：
- 权重 1: (Center, Left), (Left, Bottom-Left)
- 权重 2: (Left, Top-Left), (Center, Right), (Right, Bottom-Right)
- 权重 3: (Center, Bottom-Left), (Bottom-Left, Bottom-Right)
- 权重 4: (Center, Top-Left), (Center, Top-Right), (Top-Left, Top-Right)
- 权重 5: (Top-Right, Right)
- 依次选边（避免回路）：
- 选 (Center, Left, 1) 和 (Left, Bottom-Left, 1)。
- 选 (Left, Top-Left, 2), (Center, Right, 2), (Right, Bottom-Right, 2)。
- 至此已连接 6 个点。最后需要连接 Top-Right 点。
- 在权重 4 的边中选 (Center, Top-Right, 4) 或 (Top-Left, Top-Right, 4)。
- 计算总权值：$1 + 1 + 2 + 2 + 2 + 4 = 12$。
解题套路总结：执行算法时，每选一条边都要标记两端顶点的连通性，直到所有顶点合并进同一个集合。
难度： ⭐⭐ 考点： #最小生成树 #Kruskal算法
- 设 $\mathbb{R}^*$ 为正实数集，代数系统 $\langle \mathbb{R}^*, + \rangle$、$\langle \mathbb{R}^*, \cdot \rangle$、$\langle \mathbb{R}^*, / \rangle$ 中的运算依次为普通加法、乘法和除法运算。试确定这三个代数系统是否为群？是群者，求其单位元及每个元素的逆元。
查看答案与解析
答案：
- $\langle \mathbb{R}^*, + \rangle$：不是群。
- $\langle \mathbb{R}^*, \cdot \rangle$：是群。单位元 $e=1$，逆元 $x^{-1} = 1/x$。
- $\langle \mathbb{R}^*, / \rangle$：不是群。
详细分析：
- 加法系统：正实数加法没有单位元 $0$（$0 \notin \mathbb{R}^*$），且没有加法逆元（$-x \notin \mathbb{R}^*$）。
- 乘法系统：封闭且结合；单位元 $1 \in \mathbb{R}^*$；每个 $x$ 都有 $1/x \in \mathbb{R}^*$。完全满足群的定义。
- 除法系统：不满足结合律。例如 $(8/4)/2 = 1 \neq 8/(4/2) = 4$。
难度： ⭐⭐ 考点： #群的定义 #代数系统判定
四、证明题（共 3 小题，共 20 分）
26.（8分）在自然推理系统 $P$ 中构造下述推理的证明： 前提：$p \rightarrow (q \vee r)$，$q \rightarrow s$，$p \wedge \neg s$ 结论：$r$
查看答案与解析
证明步骤：
- $p \wedge \neg s$ （前提引入）
- $p$ （由1，化简律）
- $p \rightarrow (q \vee r)$ （前提引入）
- $q \vee r$ （由2, 3，假言推理 MP）
- $\neg s$ （由1，化简律）
- $q \rightarrow s$ （前提引入）
- $\neg q$ （由5, 6，拒取式推理 MT）
- $r$ （由4, 7，析取三段论 DS） 得证。
解题套路总结：看到析取结论（$q \vee r$），核心思想是利用否定其中一个分量（$\neg q$）来推出另一个分量（$r$）。
难度： ⭐⭐ 考点： #命题逻辑推理 #自然推理系统
27.（6分）设 $\langle G, * \rangle$ 是群，$H = \{a \mid a \in G \wedge \forall g \in G, a * g = g * a\}$，则 $\langle H, * \rangle$ 是 $G$ 的子群。
查看答案与解析
证明：
- 非空性：单位元 $e$ 满足 $e*g = g*e = g$，故 $e \in H$。
- 封闭性：设 $a, b \in H$。则对 $\forall g \in G$： $(a*b)*g = a*(b*g) = a*(g*b) = (a*g)*b = (g*a)*b = g*(a*b)$。故 $a*b \in H$。
- 逆元存在性：设 $a \in H$。对 $a*g = g*a$ 两边同时左乘 $a^{-1}$ 右乘 $a^{-1}$ 得： $a^{-1}*(a*g)*a^{-1} = a^{-1}*(g*a)*a^{-1} \implies g*a^{-1} = a^{-1}*g$。故 $a^{-1} \in H$。 结论：$H$ 是 $G$ 的子群（称为群的中心）。
难度： ⭐⭐⭐ 考点： #子群判定 #群中心
28.（6分）设 $G$ 是 $n (\geq 3)$ 阶 $m$ 条边、$r$ 个面的极大平面图，则 $r = 2n - 4$。
查看答案与解析
证明：
- 基础关系：由欧拉公式有 $n - m + r = 2$。
- 极大平面图性质：所有面均为三角形面，故有 $3r = 2m$。
- 代入化简：将 $m = 1.5r$ 代入欧拉公式得： $n - 1.5r + r = 2 \implies n - 0.5r = 2 \implies r = 2n - 4$。 结论得证。
难度： ⭐⭐ 考点： #极大平面图 #欧拉公式